/*
 * AlphaSkipSearch.cpp
 *
 *  Created on: 01-09-2013
 *      Author: Krzychu
 */

#include "AlphaSkipSearch.h"

#include "Config.h"
#include "SuffixAutomaton.h"
#include "List.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ASIZE 255

AlphaSkipSearch::AlphaSkipSearch()
{

}

AlphaSkipSearch::~AlphaSkipSearch()
{

}

std::string AlphaSkipSearch::getName()
{
	return "Alpha Skip Search";
}

List** z = new List*();

void setZ(int node, int i)
{
	List* cell = new List();

	cell->element = i;
	cell->next = z[node];

	z[node] = cell;
}

searchResult AlphaSkipSearch::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	const char* textChar = text.c_str();
	const char* patternChar = pattern.c_str();

	int b, i, j, k, logM, temp, shift, size, pos;
	int art, childNode, node, root, lastNode;
	List* current;


	logM = 0;
	temp = patternSize;
	while (temp > ASIZE)
	{
		++logM;
		temp /= ASIZE;
	}
	if (logM == 0)
	{
		logM = 1;
	}

	/* Preprocessing */
	size = 2 + (2 * patternSize - logM + 1) * logM;
	SuffixAutomaton* trie = new SuffixAutomaton(size, size * ASIZE);

	root = trie->getInitial();
	art = trie->newVertex();
	trie->setSuffixLink(root, art);
	node = trie->newVertex();
	trie->setTarget(root, pattern[0], node);
	trie->setSuffixLink(node, root);
	for (i = 1; i < logM; ++i)
	{
		node = trie->addNode(art, node, pattern[i]);
	}
	pos = 0;
	setZ(node, pos);
	pos++;
	for (i = logM; i < patternSize - 1; ++i)
	{
		node = trie->getSuffixLink(node);
		childNode = trie->getTarget(node, pattern[i]);
		if (childNode == trie->getUndefined())
		{
			node = trie->addNode(art, node, pattern[i]);
		}
		else
		{
			node = childNode;
		}
		setZ(node, pos);
		pos++;
	}
	node = trie->getSuffixLink(node);
	childNode = trie->getTarget(node, pattern[i]);
	if (childNode == trie->getUndefined())
	{
		lastNode = trie->newVertex();
		trie->setTarget(node, pattern[patternSize - 1], lastNode);
		node = lastNode;
	}
	else
	{
		node = childNode;
	}
	setZ(node, pos);

	/* Searching */
	shift = patternSize - logM + 1;
	for (j = patternSize + 1 - logM; j < textSize - logM; j += shift)
	{
		result.iterationsTaken++;

		node = root;
		for (k = 0; node != trie->getUndefined() && k < logM; ++k)
		{
			node = trie->getTarget(node, text[j + k]);
		}
		if (node != trie->getUndefined())
		{
			for (current = z[node]; ; current = current->next)
			{
				b = j - current->element;
				if (pattern[0] == text[b] && memcmp(patternChar + 1, textChar + b + 1, patternSize - 1) == 0)
				{
					result.positionsFound.push_back(b);
					if (Config::getInstance()->getFindOneOccurence())
					{
						return result;
					}
				}

				if (current->next == 0x0 || current->next->element == current->getUndefined())
				{
					break;
				}
			}
		}
	}
	free(z);

	return result;
}

